{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Good Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findGoodStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到所有好字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度为 <code>n</code>&nbsp;的字符串&nbsp;<code>s1</code> 和&nbsp;<code>s2</code>&nbsp;，以及一个字符串&nbsp;<code>evil</code>&nbsp;。请你返回 <strong>好字符串&nbsp;</strong>的数目。</p>\n",
    "\n",
    "<p><strong>好字符串</strong>&nbsp;的定义为：它的长度为&nbsp;<code>n</code>&nbsp;，字典序大于等于&nbsp;<code>s1</code>&nbsp;，字典序小于等于&nbsp;<code>s2</code>&nbsp;，且不包含&nbsp;<code>evil</code>&nbsp;为子字符串。</p>\n",
    "\n",
    "<p>由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, s1 = &quot;aa&quot;, s2 = &quot;da&quot;, evil = &quot;b&quot;\n",
    "<strong>输出：</strong>51 \n",
    "<strong>解释：</strong>总共有 25 个以 &#39;a&#39; 开头的好字符串：&quot;aa&quot;，&quot;ac&quot;，&quot;ad&quot;，...，&quot;az&quot;。还有 25 个以 &#39;c&#39; 开头的好字符串：&quot;ca&quot;，&quot;cc&quot;，&quot;cd&quot;，...，&quot;cz&quot;。最后，还有一个以 &#39;d&#39; 开头的好字符串：&quot;da&quot;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 8, s1 = &quot;leetcode&quot;, s2 = &quot;leetgoes&quot;, evil = &quot;leet&quot;\n",
    "<strong>输出：</strong>0 \n",
    "<strong>解释：</strong>所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 &quot;leet&quot; 开头。所以没有好字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, s1 = &quot;gx&quot;, s2 = &quot;gz&quot;, evil = &quot;x&quot;\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s1.length == n</code></li>\n",
    "\t<li><code>s2.length == n</code></li>\n",
    "\t<li><code>s1 &lt;= s2</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= evil.length &lt;= 50</code></li>\n",
    "\t<li>所有字符串都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-good-strings](https://leetcode.cn/problems/find-all-good-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-good-strings](https://leetcode.cn/problems/find-all-good-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n\"aa\"\\n\"da\"\\n\"b\"', '8\\n\"leetcode\"\\n\"leetgoes\"\\n\"leet\"', '2\\n\"gx\"\\n\"gz\"\\n\"x\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        if s1>s2:return 0\n",
    "        mod = 10**9+7\n",
    "        nxt = [0]\n",
    "        x = 1\n",
    "        t = 0\n",
    "        while x<len(evil):\n",
    "            if evil[t] == evil[x]:\n",
    "                t+=1\n",
    "                x+=1\n",
    "                nxt.append(t)\n",
    "            elif t:\n",
    "                t = nxt[t-1]\n",
    "            else:\n",
    "                nxt.append(0)\n",
    "                x+=1\n",
    "\n",
    "        @cache\n",
    "        def f(i,is_limit,is_limit_down,pos):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            lower = s1[i] if is_limit_down else 'a'\n",
    "            lower = ord(lower)-ord('a')\n",
    "            upper = s2[i] if is_limit else 'z'\n",
    "            upper = ord(upper)-ord('a')\n",
    "            for d in range(lower,upper+1):\n",
    "                cur_pos = pos\n",
    "                tar = chr(d+ord('a'))\n",
    "                if tar == evil[pos]:\n",
    "                    cur_pos = cur_pos+1\n",
    "                    if cur_pos == len(evil):continue\n",
    "                    res += f(i+1,d==upper and is_limit,d==lower and is_limit_down,cur_pos)\n",
    "                else:\n",
    "                    while cur_pos:\n",
    "                        cur_pos = nxt[cur_pos-1]\n",
    "                        if evil[cur_pos] == tar:\n",
    "                            cur_pos+=1\n",
    "                            break\n",
    "                    res += f(i+1,d==upper and is_limit,d==lower and is_limit_down,cur_pos)\n",
    "            \n",
    "\n",
    "                res = res%mod\n",
    "         \n",
    "               \n",
    "            return res\n",
    "\n",
    "        return f(0,True,True,0)\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        sn, en = len(s1), len(evil)\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        ne = [0] * (en + 1)\n",
    "        ne[0] = j = -1\n",
    "        i = 0\n",
    "        while i < en:\n",
    "            while j != -1 and evil[i] != evil[j]: j = ne[j]\n",
    "            i += 1\n",
    "            j += 1\n",
    "            ne[i] = j\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dfs(si=0, ei=0, lt=1, rt=1):\n",
    "            if ei == en: return 0\n",
    "            if si == sn: return 1\n",
    "            \n",
    "            l = s1[si] if lt else 'a'\n",
    "            r = s2[si] if rt else 'z'\n",
    "            res = 0\n",
    "            for i in range(ord(l), ord(r) + 1):\n",
    "                t = ei\n",
    "                while t != -1 and evil[t] != chr(i):\n",
    "                    t = ne[t]\n",
    "                res += dfs(si + 1, t + 1, lt and (i == ord(l)), rt and (i == ord(r))) \n",
    "            return res % mod\n",
    "        \n",
    "        return dfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        match = self.build_match(evil)\n",
    "        @cache\n",
    "        def f(i: int, cur: int, is_limit1: bool, is_limit2: bool):\n",
    "            if cur == len(evil): return 0\n",
    "            if i == n: return 1\n",
    "            res = 0\n",
    "            low = s1[i] if is_limit1 else 'a'\n",
    "            up = s2[i] if is_limit2 else 'z'\n",
    "            for digit in range(ord(low), ord(up) + 1):\n",
    "                d = chr(digit)\n",
    "                if d == evil[cur]:\n",
    "                    res = (res + f(i + 1, cur + 1, is_limit1 and d == low, is_limit2 and d == up)) % MOD\n",
    "                else:  # ===================和当前位匹配不上，不代表就要从0开始 。==================================\n",
    "                    tmp = cur\n",
    "                    while tmp and evil[tmp] != d: tmp = match[tmp - 1]\n",
    "                    if evil[tmp] == d: tmp += 1\n",
    "                    res = (res + f(i + 1, tmp, is_limit1 and d == low, is_limit2 and d == up)) % MOD\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True, True)\n",
    "\n",
    "\n",
    "    def build_match(self, s: str) -> List[int]:\n",
    "        match = [0] * len(s)\n",
    "        c = 0\n",
    "        for i in range(1, len(s)):\n",
    "            v = s[i]\n",
    "            while c and v != s[c]:\n",
    "                c = match[c - 1]\n",
    "            if v == s[c]:\n",
    "                c += 1\n",
    "            match[i] = c\n",
    "        return match\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        next = [[0] * 26 for i in range(len(evil))]\n",
    "        for i in range(len(evil)):\n",
    "            for j in range(i + 1):\n",
    "                if evil[:j] == evil[i - j:i]:\n",
    "                    next[i][ord(evil[j]) - 97] = j + 1\n",
    "        @cache\n",
    "        def dfs(i, flag1, flag2, k):\n",
    "            if k == len(evil):\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            low = -1 if flag1 else ord(s1[i]) - 97\n",
    "            high = 26 if flag2 else ord(s2[i]) - 97\n",
    "            for j in range(low + 1, high):\n",
    "                res += dfs(i + 1, 1, 1, next[k][j])\n",
    "            if low != high:\n",
    "                if not flag1:\n",
    "                    res += dfs(i + 1, 0, 1, next[k][low])\n",
    "                if not flag2:\n",
    "                    res += dfs(i + 1, 1, 0, next[k][high])\n",
    "            else:\n",
    "                res += dfs(i + 1, flag1, flag2, next[k][low])\n",
    "            return res % (10 ** 9 + 7)\n",
    "        return dfs(0, 0, 0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        match = self.build_match(evil)\n",
    "        @cache\n",
    "        def f(i: int, cur: int, is_limit1: bool, is_limit2: bool):\n",
    "            if cur == len(evil): return 0\n",
    "            if i == n: return 1\n",
    "            res = 0\n",
    "            low = s1[i] if is_limit1 else 'a'\n",
    "            up = s2[i] if is_limit2 else 'z'\n",
    "            for digit in range(ord(low), ord(up) + 1):\n",
    "                d = chr(digit)\n",
    "                if d == evil[cur]:\n",
    "                    res = (res + f(i + 1, cur + 1, is_limit1 and d == low, is_limit2 and d == up)) % MOD\n",
    "                else:  # ===================和当前位匹配不上，不代表就要从0开始 。==================================\n",
    "                    tmp = cur\n",
    "                    while tmp and evil[tmp] != d: tmp = match[tmp - 1]\n",
    "                    if tmp == 0 and evil[tmp] != d: tmp = -1\n",
    "                    res = (res + f(i + 1, tmp + 1, is_limit1 and d == low, is_limit2 and d == up)) % MOD\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True, True)\n",
    "\n",
    "\n",
    "    def build_match(self, s: str) -> List[int]:\n",
    "        match = [0] * len(s)\n",
    "        c = 0\n",
    "        for i in range(1, len(s)):\n",
    "            v = s[i]\n",
    "            while c and v != s[c]:\n",
    "                c = match[c - 1]\n",
    "            if v == s[c]:\n",
    "                c += 1\n",
    "            match[i] = c\n",
    "        return match\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"@lru_cache 装饰器是 Python 语言提供的可供记忆化搜索的利器\n",
    "    相当于将该参数的（输入，输出）对缓存起来\n",
    "    在以相同的输入调用该函数时，就可以避免计算，直接返回输出\n",
    "    \"\"\"\n",
    "    \n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def getTrans(stats, ch):\n",
    "            \"\"\"这是计算关于 stats 的转移函数\n",
    "            输入为 stats 和 d\n",
    "            输出为转移的结果 g_s(stats, d)\"\"\"\n",
    "\n",
    "            u = ord(ch) - 97\n",
    "            # 这是 KMP 算法的一部分\n",
    "            # 把 evil 看作「模式串」，stats 看作「主串」匹配到的位置\n",
    "            while stats > 0 and evil[stats] != ch:\n",
    "                stats = fail[stats - 1]\n",
    "            return stats + 1 if evil[stats] == ch else 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, stats, bound):\n",
    "            \"\"\"这是用来进行记忆化搜索的函数\n",
    "            输入为 pos, stats 和 bound\n",
    "            输出为 f[pos][stats][bound]\"\"\"\n",
    "\n",
    "            # 如果匹配到了 evil 的末尾\n",
    "            # 说明字符串不满足要求了\n",
    "            # 返回 0\n",
    "            if stats == len(evil):\n",
    "                return 0\n",
    "            # 如果匹配到了上下界的末尾\n",
    "            # 说明找到了一个满足要求的字符串\n",
    "            # 返回 1\n",
    "            if pos == len(s1):\n",
    "                return 1\n",
    "            \n",
    "            ans = 0\n",
    "            # 计算第 pos 位可枚举的字符下界\n",
    "            l = (ord(s1[pos]) if bound & 1 else ord('a'))\n",
    "            # 计算第 pos 位可枚举的字符上界\n",
    "            r = (ord(s2[pos]) if bound & 2 else ord('z'))\n",
    "            for u in range(l, r + 1):\n",
    "                ch = chr(u)\n",
    "                nxt_stats = getTrans(stats, ch)\n",
    "                # 这里写得较为复杂\n",
    "                # 本质上就是关于 bound 的转移函数\n",
    "                # 可以根据自己的理解编写\n",
    "                nxt_bound = (ch == s1[pos] if bound & 1 else 0) ^ ((ch == s2[pos]) << 1 if bound & 2 else 0)\n",
    "                ans += dfs(pos + 1, nxt_stats, nxt_bound)\n",
    "            return ans % 1000000007\n",
    "\n",
    "        m = len(evil)\n",
    "        # 这是用来帮助计算关于 stats 的转移函数的 fail 数组\n",
    "        fail = [0] * m\n",
    "        # 这是 KMP 算法的一部分\n",
    "        # 把「evil」看作模式串，得到它的 fail[] 数组\n",
    "        for i in range(1, m):\n",
    "            j = fail[i - 1]\n",
    "            while j > 0 and evil[j] != evil[i]:\n",
    "                j = fail[j - 1]\n",
    "            if evil[j] == evil[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        # 答案即为 f[0][0][3]\n",
    "        return dfs(0, 0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"@lru_cache 装饰器是 Python 语言提供的可供记忆化搜索的利器\n",
    "    相当于将该参数的（输入，输出）对缓存起来\n",
    "    在以相同的输入调用该函数时，就可以避免计算，直接返回输出\n",
    "    \"\"\"\n",
    "    \n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def getTrans(stats, ch):\n",
    "            \"\"\"这是计算关于 stats 的转移函数\n",
    "            输入为 stats 和 d\n",
    "            输出为转移的结果 g_s(stats, d)\"\"\"\n",
    "\n",
    "            u = ord(ch) - 97\n",
    "            # 这是 KMP 算法的一部分\n",
    "            # 把 evil 看作「模式串」，stats 看作「主串」匹配到的位置\n",
    "            while stats > 0 and evil[stats] != ch:\n",
    "                stats = fail[stats - 1]\n",
    "            return stats + 1 if evil[stats] == ch else 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, stats, bound):\n",
    "            \"\"\"这是用来进行记忆化搜索的函数\n",
    "            输入为 pos, stats 和 bound\n",
    "            输出为 f[pos][stats][bound]\"\"\"\n",
    "\n",
    "            # 如果匹配到了 evil 的末尾\n",
    "            # 说明字符串不满足要求了\n",
    "            # 返回 0\n",
    "            if stats == len(evil):\n",
    "                return 0\n",
    "            # 如果匹配到了上下界的末尾\n",
    "            # 说明找到了一个满足要求的字符串\n",
    "            # 返回 1\n",
    "            if pos == len(s1):\n",
    "                return 1\n",
    "            \n",
    "            ans = 0\n",
    "            # 计算第 pos 位可枚举的字符下界\n",
    "            l = (ord(s1[pos]) if bound & 1 else ord('a'))\n",
    "            # 计算第 pos 位可枚举的字符上界\n",
    "            r = (ord(s2[pos]) if bound & 2 else ord('z'))\n",
    "            for u in range(l, r + 1):\n",
    "                ch = chr(u)\n",
    "                nxt_stats = getTrans(stats, ch)\n",
    "                # 这里写得较为复杂\n",
    "                # 本质上就是关于 bound 的转移函数\n",
    "                # 可以根据自己的理解编写\n",
    "                nxt_bound = (ch == s1[pos] if bound & 1 else 0) ^ ((ch == s2[pos]) << 1 if bound & 2 else 0)\n",
    "                ans += dfs(pos + 1, nxt_stats, nxt_bound)\n",
    "            return ans % 1000000007\n",
    "\n",
    "        m = len(evil)\n",
    "        # 这是用来帮助计算关于 stats 的转移函数的 fail 数组\n",
    "        fail = [0] * m\n",
    "        # 这是 KMP 算法的一部分\n",
    "        # 把「evil」看作模式串，得到它的 fail[] 数组\n",
    "        for i in range(1, m):\n",
    "            j = fail[i - 1]\n",
    "            while j > 0 and evil[j] != evil[i]:\n",
    "                j = fail[j - 1]\n",
    "            if evil[j] == evil[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        # 答案即为 f[0][0][3]\n",
    "        return dfs(0, 0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        MOD = int(1e9) + 7\n",
    "        m = len(evil)\n",
    "\n",
    "        mp = [0] * m\n",
    "\n",
    "        for i in range(1, m):\n",
    "            j = mp[i - 1]\n",
    "            while j > 0 and evil[j] != evil[i]:\n",
    "                j = mp[j - 1]\n",
    "\n",
    "            if evil[i] == evil[j]:\n",
    "                mp[i] = j + 1\n",
    "\n",
    "        @cache\n",
    "        def jump(idx, c):\n",
    "            j = idx\n",
    "\n",
    "            while j > 0 and ord(evil[j]) != c:\n",
    "                j = mp[j - 1]\n",
    "\n",
    "            if ord(evil[j]) == c:\n",
    "                return j + 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dp(idx, stat, bound): \n",
    "            if stat == len(evil):\n",
    "                return 0\n",
    "\n",
    "            if idx == n:\n",
    "                return 1\n",
    "\n",
    "            if bound == 0:\n",
    "                start = ord('a')\n",
    "                end = ord('z')\n",
    "            elif bound == 1:\n",
    "                start = ord(s1[idx])\n",
    "                end = ord('z')\n",
    "            elif bound == 2:\n",
    "                start = ord('a')\n",
    "                end = ord(s2[idx])\n",
    "            else:\n",
    "                start = ord(s1[idx])\n",
    "                end = ord(s2[idx])\n",
    "\n",
    "            ret = 0\n",
    "\n",
    "            for i in range(start, end + 1):\n",
    "                if bound == 0:\n",
    "                    nb = 0\n",
    "                elif bound == 1:\n",
    "                    if i == start:\n",
    "                        nb = 1\n",
    "                    else:\n",
    "                        nb = 0\n",
    "                elif bound == 2:\n",
    "                    if i == end:\n",
    "                        nb = 2\n",
    "                    else:\n",
    "                        nb = 0\n",
    "                else:\n",
    "                    if start == end == i:\n",
    "                        nb = 3\n",
    "                    elif i == start:\n",
    "                        nb = 1\n",
    "                    elif i == end:\n",
    "                        nb = 2\n",
    "                    else:\n",
    "                        nb = 0\n",
    "\n",
    "                ns = jump(stat, i)\n",
    "\n",
    "                ret += dp(idx + 1, ns, nb)\n",
    "\n",
    "                ret %= MOD\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, 0, 3)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def nxt(c, eidx):\n",
    "            for j in range(eidx+2)[::-1]:\n",
    "                if (evil[:eidx]+c)[-j:] == evil[:j]:\n",
    "                    return j\n",
    "            return 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, lbound, ubound, eidx):\n",
    "            if eidx == m: return 0\n",
    "            if idx == n: return 1\n",
    "            low = ord(s1[idx])-ord(\"a\") if lbound else 0\n",
    "            up = ord(s2[idx])-ord(\"a\") if ubound else 25\n",
    "            ret = 0\n",
    "            for i in range(low, up+1):\n",
    "                nlbound = lbound and i == low\n",
    "                nubound = ubound and i == up\n",
    "                c = chr(i+ord(\"a\"))\n",
    "                ret += dfs(idx+1, nlbound, nubound, nxt(c, eidx))\n",
    "                # if evil[eidx] == c:\n",
    "                #     ret += dfs(idx+1, nlbound, nubound, eidx+1)\n",
    "                # else:\n",
    "                #     ret += dfs(idx+1, nlbound, nubound, nxt(c, eidx))\n",
    "            return ret%mod\n",
    "\n",
    "        m = len(evil)\n",
    "        mod = 10**9+7\n",
    "        return dfs(0, True, True, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def nxt(c, eidx):\n",
    "            for j in range(eidx+1)[::-1]:\n",
    "                if (evil[:eidx]+c)[-j:] == evil[:j]:\n",
    "                    return j\n",
    "            return 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, lbound, ubound, eidx):\n",
    "            if eidx == m: return 0\n",
    "            if idx == n: return 1\n",
    "            low = ord(s1[idx])-ord(\"a\") if lbound else 0\n",
    "            up = ord(s2[idx])-ord(\"a\") if ubound else 25\n",
    "            ret = 0\n",
    "            for i in range(low, up+1):\n",
    "                nlbound = lbound and i == low\n",
    "                nubound = ubound and i == up\n",
    "                c = chr(i+ord(\"a\"))\n",
    "                # ret += dfs(idx+1, nlbound, nubound, nxt(c, eidx))\n",
    "                if evil[eidx] == c:\n",
    "                    ret += dfs(idx+1, nlbound, nubound, eidx+1)\n",
    "                else:\n",
    "                    ret += dfs(idx+1, nlbound, nubound, nxt(c, eidx))\n",
    "            return ret%mod\n",
    "\n",
    "        m = len(evil)\n",
    "        mod = 10**9+7\n",
    "        return dfs(0, True, True, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        m = len(evil)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = ord('a')\n",
    "        def prefix_function(s) -> list[int]:\n",
    "            n = len(s)\n",
    "            next = [0] * n\n",
    "            for i in range(1, n):\n",
    "                j = next[i - 1]\n",
    "                while j > 0 and s[j] != s[i]:\n",
    "                    j = next[j - 1]\n",
    "                if s[j] == s[i]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            return next\n",
    "        pi = prefix_function(evil)\n",
    "        def f(s: str):\n",
    "            @cache\n",
    "            def dfs(i: int, cnt: int, is_limit: bool):\n",
    "                if i == n:\n",
    "                    return 1\n",
    "                res = 0\n",
    "                up = ord(s[i]) - a if is_limit else 25\n",
    "                for d in range(up + 1):\n",
    "                    c = cnt\n",
    "                    while c > 0 and ord(evil[c]) - a != d:\n",
    "                        c = pi[c - 1]\n",
    "                    if ord(evil[c]) - a == d:\n",
    "                        c += 1\n",
    "                    if c == m: continue\n",
    "                    res += dfs(i + 1, c, is_limit and d == up)\n",
    "                    res %= MOD\n",
    "                return res\n",
    "            return dfs(0, 0, True)\n",
    "        return (f(s2) - f(s1) + int(evil not in s1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        def prep(s: str):\n",
    "            _n = len(s)\n",
    "            j = 0\n",
    "            pi = [0] * _n\n",
    "            for i in range(1, _n):\n",
    "                while j and s[j] != s[i]: j = pi[j - 1]\n",
    "                if s[i] == s[j]: j += 1\n",
    "                pi[i] = j\n",
    "            return pi\n",
    "        kmp = prep(evil)\n",
    "        #print(kmp)\n",
    "        def calc(s):\n",
    "            @cache\n",
    "            def dfs(idx, isLimit, todo):\n",
    "                if todo == len(evil): return 0\n",
    "                if idx == len(s): return 1\n",
    "                upper = ord(s[idx]) if isLimit else ord('z')\n",
    "                ans = 0\n",
    "                for x in range(ord('a'), upper + 1):\n",
    "                    x = chr(x)\n",
    "                    j = todo\n",
    "                    while j > 0 and evil[j] != x:\n",
    "                        j = kmp[j - 1]\n",
    "                    if x == evil[j]: j += 1\n",
    "                    ans += dfs(idx + 1, isLimit and ord(x) == upper, j)\n",
    "                ans %= MOD\n",
    "                return ans\n",
    "            return dfs(0, 1, 0)\n",
    "        return (calc(s2) - calc(s1) + int(evil not in s1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "         \n",
    "\n",
    "            m = [0 for _ in range(len(evil))]\n",
    "            l = 0\n",
    "            for i in range(1,len(evil)):\n",
    "                ch = evil[i]\n",
    "                while l > 0 and evil[l] != ch:\n",
    "                    l = m[l - 1]\n",
    "                if evil[l] == ch:\n",
    "                    l += 1\n",
    "                m[i] = l\n",
    "            MOD = pow(10,9) + 7\n",
    "            def get_next(state,curch):\n",
    "                while state > 0 and evil[state] != curch:\n",
    "                    state = m[state - 1]\n",
    "                if evil[state] == curch:\n",
    "                    state += 1\n",
    "                return state\n",
    "            s1 = s1[:-1] + chr(ord(s1[-1]) - 1)\n",
    "             \n",
    "            \n",
    "            def calc(s):\n",
    "                length = len(s)\n",
    "                @cache\n",
    "                def dfs(i,is_lim ,state):\n",
    "                    if i == length:\n",
    "                        return 1\n",
    "                    res = 0\n",
    "                    up = ord(s[i]) - ord(\"a\")  if is_lim else 25\n",
    "                    \n",
    "                    for j in range(0,up + 1):\n",
    "                        newch = chr(ord(\"a\") + j)\n",
    "                        \n",
    "                        news = get_next(state,newch)\n",
    "                        \n",
    "                        if news != len(evil):\n",
    "                              res = (res + dfs(i + 1,is_lim and (newch == s[i]),news)) % MOD\n",
    "                    return res\n",
    "                return dfs(0,True,0)\n",
    "            \n",
    "            \n",
    "            return (calc(s2)  + MOD - calc(s1))%MOD\n",
    "\n",
    "                        \n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "@lru_cache(None)\n",
    "def cal(upper: str, evil: str) -> int:\n",
    "    \"\"\"字典序小于等于upper且不含evil的字符串个数\"\"\"\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(index: int, isLimit: bool, hit: int) -> int:\n",
    "        \"\"\"当前在第pos位,isLimit表示是否贴合上界,hit表示匹配了多少个evil字符\"\"\"\n",
    "        if hit == m:\n",
    "            return 0\n",
    "        if index == n:\n",
    "            return 1\n",
    "        res = 0\n",
    "        up = upper[index] if isLimit else 'z'\n",
    "        for cur in range(97, ord(up) + 1):\n",
    "            select = chr(cur)\n",
    "            nextHit = hit\n",
    "\n",
    "            while nextHit > 0 and select != evil[nextHit]:  # 1. 前进：匹配不成功nextHit往右直接走到最长公共后缀的位置\n",
    "                nextHit = evilNext[nextHit - 1]\n",
    "            if select == evil[nextHit]:  # 2. 匹配：匹配成功nextHit往右走一步\n",
    "                nextHit += 1\n",
    "\n",
    "            res += dfs(index + 1, (isLimit and select == up), nextHit)\n",
    "            res %= MOD\n",
    "        return res\n",
    "\n",
    "    n, m = len(upper), len(evil)\n",
    "    evilNext = getNext(evil)\n",
    "    return dfs(0, True, 0)\n",
    "\n",
    "\n",
    "@lru_cache(None)\n",
    "def getNext(needle: str) -> List[int]:\n",
    "    \"\"\"kmp O(n)求 `needle`串的 `next`数组\n",
    "\n",
    "    `next[i]`表示`[:i+1]`这一段字符串中最长公共前后缀(不含这一段字符串本身)的长度\n",
    "    \"\"\"\n",
    "    next = [0] * len(needle)\n",
    "    j = 0\n",
    "\n",
    "    for i in range(1, len(needle)):\n",
    "        while j and needle[i] != needle[j]: \n",
    "            j = next[j - 1]\n",
    "        if needle[i] == needle[j]:\n",
    "            j += 1\n",
    "        next[i] = j\n",
    "\n",
    "    return next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        return (cal(s2, evil) - cal(s1, evil) + int(evil not in s1)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        a=ord('a')\n",
    "        z=ord('z')\n",
    "        \n",
    "        arr_e=list(map(ord,evil))\n",
    "        len_e=len(evil)\n",
    "        next=[0]*len_e\n",
    "        for i in range(1,len_e):\n",
    "            j=next[i-1]\n",
    "            while j>0 and evil[i]!=evil[j]:\n",
    "                j=next[j-1]\n",
    "            if evil[i]==evil[j]:\n",
    "                next[i]=j+1\n",
    "\n",
    "        def good(s):\n",
    "            arr=list(map(ord,s))\n",
    "            len_a=len(arr)\n",
    "\n",
    "            @cache\n",
    "            def f(i,skip,reach,e):\n",
    "                if e==len_e:\n",
    "                    return 0\n",
    "                if i==len_a:\n",
    "                    return 0 if skip else 1\n",
    "                limit=arr[i] if reach else z\n",
    "                ans=0\n",
    "                if skip:\n",
    "                    ans+=f(i+1,True,False,0)\n",
    "                for c in range(a,limit+1):\n",
    "                    ee=e\n",
    "                    while ee>0 and arr_e[ee]!=c:\n",
    "                        ee=next[ee-1]\n",
    "                    if arr_e[ee]==c:\n",
    "                        ee+=1\n",
    "                    ans+=f(i+1,False,reach and c==limit,ee)\n",
    "                return ans%int(1e9+7)\n",
    "\n",
    "            return f(0,True,True,0)\n",
    "\n",
    "        return (good(s2)-good(s1)+int(evil not in s1))%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        a=ord('a')\n",
    "        z=ord('z')\n",
    "        arr_e=list(map(ord,evil))\n",
    "        len_e=len(evil)\n",
    "        next=[0]*len_e\n",
    "        for i in range(1,len_e):\n",
    "            j=next[i-1]\n",
    "            while j>0 and evil[i]!=evil[j]:\n",
    "                j=next[j-1]\n",
    "            if evil[i]==evil[j]:\n",
    "                next[i]=j+1\n",
    "\n",
    "        def good(s):\n",
    "            # print(f'======= {s}')\n",
    "            arr=list(map(ord,s))\n",
    "            len_a=len(arr)\n",
    "\n",
    "            @cache\n",
    "            def f(i,skip,reach,e):\n",
    "                if e==len_e:\n",
    "                    # print('==== fail evil')\n",
    "                    return 0\n",
    "                if i==len_a:\n",
    "                    return 0 if skip else 1\n",
    "                limit=arr[i] if reach else z\n",
    "                ans=0\n",
    "                if skip:\n",
    "                    # print('*'*i)\n",
    "                    ans+=f(i+1,True,False,0)\n",
    "                for c in range(a,limit+1):\n",
    "                    ee=e\n",
    "                    while ee>0 and arr_e[ee]!=c:\n",
    "                        ee=next[ee-1]\n",
    "                    if arr_e[ee]==c:\n",
    "                        ee+=1\n",
    "                    # print('_'*i+f'{chr(c)}')\n",
    "                    ans+=f(i+1,False,reach and c==limit,ee)\n",
    "                return ans%int(1e9+7)\n",
    "\n",
    "            return f(0,True,True,0)\n",
    "\n",
    "        # print(good(s2),good(s1))\n",
    "        return (good(s2)-good(s1)+int(evil not in s1))%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def calc_tot(s):\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                res = (res * 26 + ord(s[i]) - ord('a')) % MOD\n",
    "            return res + 1\n",
    "\n",
    "        midstr_tot = (calc_tot(s2) - calc_tot(s1) + 1) % MOD\n",
    "\n",
    "        def build_nxt_table(s):\n",
    "            kmp_table = [0] * len(s)\n",
    "            i, j = 1, 0\n",
    "            while i < len(s):\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                    kmp_table[i] = j\n",
    "                    i += 1\n",
    "                elif j > 0:\n",
    "                    j = kmp_table[j - 1]\n",
    "                else:\n",
    "                    j = 0\n",
    "                    kmp_table[i] = j\n",
    "                    i += 1\n",
    "\n",
    "            nxt = [[0] * 26 for _ in range(len(s))]\n",
    "            for j in range(len(s)):\n",
    "                for i_ord in range(26):\n",
    "                    iter_j = j\n",
    "                    while True:\n",
    "                        if i_ord == ord(s[iter_j]) - ord('a'):\n",
    "                            nxt[j][i_ord] = iter_j + 1\n",
    "                            break\n",
    "                        elif iter_j > 0:\n",
    "                            iter_j = kmp_table[iter_j - 1]\n",
    "                        else:\n",
    "                            nxt[j][i_ord] = 0\n",
    "                            break\n",
    "            return nxt\n",
    "\n",
    "        nxt = build_nxt_table(evil)\n",
    "\n",
    "        N_e = len(evil)\n",
    "        @cache\n",
    "        def dfs(i, j, is_limit, tag):\n",
    "            s = s1 if tag else s2\n",
    "            if j == N_e and i == n:\n",
    "                return 1\n",
    "            elif j == N_e and is_limit:\n",
    "                return calc_tot(s[i:])\n",
    "            elif j == N_e and not is_limit:\n",
    "                return pow(26, n - i, MOD)\n",
    "            elif i == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            end = ord(s[i]) - ord('a') if is_limit else 25\n",
    "            for k_ord in range(end + 1):\n",
    "                nxt_j = nxt[j][k_ord]\n",
    "                res = (res + dfs(i + 1, nxt_j, is_limit and k_ord == end, tag)) % MOD\n",
    "            return res\n",
    "\n",
    "        midstr_w_evil = dfs(0, 0, True, False) - dfs(0, 0, True, True)\n",
    "        if s1.find(evil) >= 0:\n",
    "            midstr_w_evil += 1\n",
    "\n",
    "        midstr_wo_evil = (midstr_tot - midstr_w_evil) % MOD\n",
    "        return midstr_wo_evil"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        if s1>s2:return 0\n",
    "        mod = 10**9+7\n",
    "        nxt = [0]\n",
    "        x = 1\n",
    "        t = 0\n",
    "        while x<len(evil):\n",
    "            if evil[t] == evil[x]:\n",
    "                t+=1\n",
    "                x+=1\n",
    "                nxt.append(t)\n",
    "            elif t:\n",
    "                t = nxt[t-1]\n",
    "            else:\n",
    "                nxt.append(0)\n",
    "                x+=1\n",
    "\n",
    "        # @cache\n",
    "        # def f(i,is_limit,is_limit_down,pos):\n",
    "        #     if i == n:\n",
    "        #         return 1\n",
    "        #     res = 0\n",
    "        #     lower = s1[i] if is_limit_down else 'a'\n",
    "        #     lower = ord(lower)-ord('a')\n",
    "        #     upper = s2[i] if is_limit else 'z'\n",
    "        #     upper = ord(upper)-ord('a')\n",
    "        #     for d in range(lower,upper+1):\n",
    "        #         cur_pos = pos\n",
    "        #         tar = chr(d+ord('a'))\n",
    "        #         if tar == evil[pos]:\n",
    "        #             cur_pos = cur_pos+1\n",
    "        #             if cur_pos == len(evil):continue\n",
    "        #             res += f(i+1,d==upper and is_limit,d==lower and is_limit_down,cur_pos)\n",
    "        #         else:\n",
    "        #             while cur_pos:\n",
    "        #                 cur_pos = nxt[cur_pos-1]\n",
    "        #                 if evil[cur_pos] == tar:\n",
    "        #                     cur_pos+=1\n",
    "        #                     break\n",
    "        #             res += f(i+1,d==upper and is_limit,d==lower and is_limit_down,cur_pos)\n",
    "        #         res = res%mod\n",
    "        #     return res\n",
    "\n",
    "        # return f(0,True,True,0)\n",
    "        \n",
    "        @cache\n",
    "        def f(s,i,is_limit,pos):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            upper = s[i] if is_limit else 'z'\n",
    "            upper = ord(upper)-ord('a')\n",
    "            for d in range(0,upper+1):\n",
    "                cur_pos = pos\n",
    "                tar = chr(d+ord('a'))\n",
    "                if tar == evil[pos]:\n",
    "                    cur_pos = cur_pos+1\n",
    "                    if cur_pos == len(evil):continue\n",
    "                    res += f(s,i+1,d==upper and is_limit,cur_pos)\n",
    "                else:\n",
    "                    while cur_pos:\n",
    "                        cur_pos = nxt[cur_pos-1]\n",
    "                        if evil[cur_pos] == tar:\n",
    "                            cur_pos+=1\n",
    "                            break\n",
    "                    res += f(s,i+1,d==upper and is_limit,cur_pos)\n",
    "                res = res%mod\n",
    "            return res\n",
    "        p = len(s1)-1\n",
    "        while p >=0 and s1[p]=='a':\n",
    "            p-=1\n",
    "            \n",
    "        \n",
    "        return (f(s2,0,True,0)%mod -  f(s1,0,True,0)%mod)%mod + (0 if evil in s1 else 1)\n",
    "\n",
    "        \n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        m = len(evil)\n",
    "        ne = [0] * m\n",
    "        i = 1; j = 0\n",
    "\n",
    "        while i < m:\n",
    "            while j > 0 and evil[i] != evil[j]:\n",
    "                j = ne[j - 1]\n",
    "            if evil[i] == evil[j]: \n",
    "                j += 1\n",
    "            ne[i] = j\n",
    "            i += 1\n",
    "\n",
    "        MOD = int(1e9+7)\n",
    "        @cache\n",
    "        def f(i: int, j: int, is_limit: bool, upper: str) -> int:\n",
    "            if j == m:\n",
    "                return 0\n",
    "            if i == len(upper):\n",
    "                return 1\n",
    "            res = 0\n",
    "            up = upper[i] if is_limit else 'z'\n",
    "            for c in range(97, ord(up) + 1):\n",
    "                x = chr(c)\n",
    "                nj = j\n",
    "                while nj > 0 and x != evil[nj]:\n",
    "                    nj = ne[nj - 1]\n",
    "                if x == evil[nj]:\n",
    "                    nj += 1\n",
    "                res += f(i + 1, nj, is_limit and x == up, upper)\n",
    "                res %= MOD\n",
    "            return res\n",
    "        return ( f(0, 0, True, s2) - f(0, 0, True, s1) + int(evil not in s1) ) % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        m = len(evil)\n",
    "        ne = [0] * m\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and evil[j] != evil[i]:\n",
    "                j = ne[j - 1]\n",
    "            if evil[j] == evil[i]:\n",
    "                j += 1\n",
    "            ne[i] = j\n",
    "        mod = int(1e9)+7\n",
    "\n",
    "        # i: 原字符串 j: evil字符串\n",
    "        @lru_cache(None)\n",
    "        def f(i: int, j: int, limit: bool, s: str):\n",
    "            if j == m:\n",
    "                return 0\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            up = s[i] if limit else 'z'\n",
    "            for c in range(97, ord(up) + 1):\n",
    "                x = chr(c) # 当前字符\n",
    "                nj = j\n",
    "                while nj > 0 and x != evil[nj]:\n",
    "                    nj = ne[nj - 1]\n",
    "                if x == evil[nj]:\n",
    "                    nj += 1\n",
    "                ans =  ( ans + f(i + 1, nj, limit and x == up, s) ) % mod\n",
    "            return ans\n",
    "        return ( f(0, 0, True, s2) - f(0, 0, True, s1) + int(evil not in s1) + mod ) % mod \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s: str, t: str, u: str) -> int:\n",
    "        k = 0\n",
    "        m = len(u)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        LPS = [0] * m\n",
    "        DP = [[[[None for _ in range(2)] for _ in range(2)]\n",
    "                      for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(1, m):\n",
    "            while k > 0 and u[k] != u[i]: k = LPS[k - 1]\n",
    "            if u[k] == u[i]: LPS[i] = k = k + 1\n",
    "        def solve(i: int, j: int, l: bool, r: bool) -> int:\n",
    "            if j == m: return 0\n",
    "            if i == n: return 1\n",
    "            if DP[i][j][l][r] != None: return DP[i][j][l][r]\n",
    "            DP[i][j][l][r] = 0\n",
    "            for c in ascii_lowercase:\n",
    "                if l and c < s[i]: continue\n",
    "                if r and c > t[i]: continue\n",
    "                x = l and c == s[i]\n",
    "                y = r and c == t[i]\n",
    "                k = j\n",
    "                while k > 0 and u[k] != c: k = LPS[k - 1]\n",
    "                if u[k] == c: k = k + 1\n",
    "                DP[i][j][l][r] += solve(i + 1, k, x, y)\n",
    "                DP[i][j][l][r] %= MOD\n",
    "            return DP[i][j][l][r]\n",
    "        return solve(0, 0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        # cacl next\n",
    "        m = len(evil)\n",
    "        ne = [0] * (m + 1)\n",
    "        j = 0\n",
    "        for i in range(2, m + 1):\n",
    "            while j != 0 and evil[i - 1] != evil[j]: j = ne[j]\n",
    "            if evil[i - 1] == evil[j]: j += 1\n",
    "            ne[i] = j\n",
    "\n",
    "\n",
    "        # bound: 现在匹配到了evil的第几个\n",
    "        @cache\n",
    "        def f(i: int, limit1: bool, limit2: bool, bound: int) -> int:\n",
    "            if bound == m: # 出现子串了，不合法\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 1 # how to filter\n",
    "            res = 0\n",
    "\n",
    "            lower = s1[i] if limit1 else 'a'\n",
    "            upper = s2[i] if limit2 else 'z'\n",
    "\n",
    "            for kk in range(ord(lower), ord(upper) + 1):\n",
    "                k = chr(kk) # 字符\n",
    "\n",
    "                # 把evil当成模式串，看长串的第bound位能匹配到哪\n",
    "                j = bound\n",
    "                while j != 0 and k != evil[j]:\n",
    "                    j = ne[j]\n",
    "                if k == evil[j]:\n",
    "                    j += 1\n",
    "\n",
    "                res += f(i+1, limit1 and k == lower, limit2 and k == upper, j)\n",
    "            return res\n",
    "        return int(f(0, True, True, 0) % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_ne(son):\n",
    "    ne = [0]\n",
    "    for i in range(1, len(son)):\n",
    "        j = ne[i - 1]\n",
    "        while j and son[i] != son[j]:\n",
    "            j = ne[j - 1]\n",
    "        if son[i] == son[j]:\n",
    "            j += 1\n",
    "        ne.append(j)\n",
    "    return ne      \n",
    "\n",
    " \n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        ne = get_ne(evil)\n",
    "        arr = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        def kmp(m, s):\n",
    "            j = 0\n",
    "            for i in range(len(m)):                 \n",
    "                while j and m[i] != s[j]:\n",
    "                    j = ne[j - 1]\n",
    "                if m[i] == s[j]:\n",
    "                    j += 1\n",
    "                if j == len(s):\n",
    "                    return i - j + 1 \n",
    "            return -1 \n",
    "        @cache                 \n",
    "        def f(i, j, up_limit, s):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            up = s[i] if up_limit else 'z'\n",
    "            for d in arr:\n",
    "                if d <= up:\n",
    "                    k = j\n",
    "                    while k and d != evil[k]:\n",
    "                        k = ne[k - 1]\n",
    "                    if d == evil[k]:\n",
    "                        k += 1\n",
    "                    if k == len(evil):\n",
    "                        continue        \n",
    "                    res += f(i + 1,k,up_limit and (d == up), s)  \n",
    "            return res\n",
    "        cnt1 = f(0,0,True,s2)\n",
    "        cnt2 = f(0,0,True,s1)\n",
    "        one = not evil in s1\n",
    "        return (cnt1 - cnt2 + one) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_ne(son):\n",
    "    ne = [0]\n",
    "    for i in range(1, len(son)):\n",
    "        j = ne[i - 1]\n",
    "        while j and son[i] != son[j]:\n",
    "            j = ne[j - 1]\n",
    "        if son[i] == son[j]:\n",
    "            j += 1\n",
    "        ne.append(j)\n",
    "    return ne      \n",
    "\n",
    " \n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        ne = get_ne(evil)\n",
    "        arr = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        def kmp(m, s):\n",
    "            j = 0\n",
    "            for i in range(len(m)):                 \n",
    "                while j and m[i] != s[j]:\n",
    "                    j = ne[j - 1]\n",
    "                if m[i] == s[j]:\n",
    "                    j += 1\n",
    "                if j == len(s):\n",
    "                    return i - j + 1 \n",
    "            return -1 \n",
    "        @cache                 \n",
    "        def f(i, j, up_limit, s):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            up = s[i] if up_limit else 'z'\n",
    "            for d in arr:\n",
    "                if d <= up:\n",
    "                    k = j\n",
    "                    while k and d != evil[k]:\n",
    "                        k = ne[k - 1]\n",
    "                    if d == evil[k]:\n",
    "                        k += 1\n",
    "                    if k == len(evil):\n",
    "                        continue        \n",
    "                    res += f(i + 1,k,up_limit and (d == up), s)  \n",
    "            return res\n",
    "        cnt1 = f(0,0,True,s2)\n",
    "        cnt2 = f(0,0,True,s1)\n",
    "        one = not evil in s1\n",
    "        return (cnt1 - cnt2 + one) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n",
    "        #KMP求next\n",
    "        e=evil\n",
    "        evil=' '+evil\n",
    "        sz=len(e)\n",
    "        ne=[0]*(sz+1)\n",
    "        j=0\n",
    "        for i in range(2,sz+1):\n",
    "            while (j and evil[i]!=evil[j+1]):\n",
    "                j=ne[j]\n",
    "            if evil[i]==evil[j+1]:\n",
    "                j+=1\n",
    "            ne[i]=j\n",
    "        @cache#i表示当前位置，j表示匹配位置\n",
    "        def f(i: int, j: int, is_limit: bool, s: str)->int:\n",
    "            if i==n:\n",
    "                return 1\n",
    "            up=ord(s[i]) if is_limit else 122\n",
    "            ans=0\n",
    "            for d in range(97,up+1):\n",
    "                x=chr(d)\n",
    "                k=j\n",
    "                while (k and x!=evil[k+1]): \n",
    "                    k=ne[k]\n",
    "                if x==evil[k+1]:\n",
    "                    k+=1\n",
    "                if k==sz:continue\n",
    "                ans+=f(i+1,k,is_limit and d==up,s)\n",
    "            return ans\n",
    "        return (f(0,0,True,s2)-f(0,0,True,s1)+(not e in s1))%(10**9+7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
